package com.linyaonan.leetcode.medium._08_09;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;

/**
 * 括号。设计一种算法，打印n对括号的所有合法的（例如，开闭一一对应）组合。
 * <p>
 * 说明：解集不能包含重复的子集。
 * <p>
 * 例如，给出 n = 3，生成结果为：
 * <p>
 * [
 * "((()))",
 * "(()())",
 * "(())()",
 * "()(())",
 * "()()()"
 * ]
 *
 * @author: Lin
 * @date: 2020/3/30
 */
public class GenerateParenthesis {

    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        if (n == 0) {
            return result;
        }

        generate(n, result, "", 0, 0);
        return result;
    }

    private void generate(int n, List<String> result, String item, int left, int right) {
        if ((left + right) == 2 * n) {
            result.add(item);
        }

        if (left < n) {
            generate(n, result, item + "(", left + 1, right);
        }

        if ((right < n) && (right < left)) {
            generate(n, result, item + ")", left, right + 1);
        }
    }
}
